Iain S. Duff

• 
  Preconditioning of Least-Squares Problems by Identifying Basic Variables
  Iain S. Duff
  We study the preconditioning of the augmented system formulation of the least squares problem $min_x || b - A x ||^2_2$, viz. $$ left[egin{array}{cc}I_m&AA^T&0end{array} ight];left[egin{array}{c}rxend{array} ight]=left[egin{array}{c}bend{array} ight], $$ where A is a sparse matrix of order $m imes n$ with full column rank and $r$ is the residual vector equal to $b - Ax$. We split the matrix $A$ into basic and non-basic parts so that $P A = left[ egin{array}{c} BN end{array} ight],$ where $P$ is a permutation matrix, and we use the preconditioner $$M = left[ egin{array}{cc} I & 0 0 & B^{-T} end{array} ight] $$ to symmetrically precondition the system to obtain, after a simple block Gaussian elimination, the reduced symmetric quasi-definite (SQD) system $$ egin{eqnarray*} left[ egin{array}{cc} I_{m-n} & N B^{-1} B^{-T}N^T & -I_n end{array} ight] ; left[ egin{array}{c} r_N B x end{array} ight] = left[ egin{array}{c} b_N-b_B end{array} ight] . end{eqnarray*} $$ We discuss the conditioning of the SQD system with some minor extensions to standard eigenanalysis, show the difficulties associated with choosing the basis matrix $B$, and discuss how sparse direct techniques can be used to choose it. We also comment on the common case where A is an incidence matrix and the basis can be chosen graphically.